package leetcode.code0980;

import leetcode.IDebug;

public class Solution implements IDebug {

//	1 表示起始方格。且只有一个起始方格。
//	2 表示结束方格，且只有一个结束方格。
//	0 表示我们可以走过的空方格。
//	-1 表示我们无法跨越的障碍。
	int startx, starty;// 开始
	int endx, endy;// 结束
	int limit;// 全部走完标记
	int way;// 路障
	int[][] grid;
	int m, n;// grid二维长度
	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	public int uniquePathsIII(int[][] grid) {
		m = grid.length;
		n = grid[0].length;
		int limitSize = m * n;
		limit = (1 << limitSize) - 1;
		way = 0;
		this.grid = grid;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = grid[i][j];
				if (cur == -1) {
					int index = this.index(i, j, n);
					way |= 1 << index;
				} else if (cur == 1) {
					startx = i;
					starty = j;
				} else if (cur == 2) {
					endx = i;
					endy = j;
				}
			}
		}
		Integer[][][] dp = new Integer[m + 1][n + 1][1 << limitSize];
		return this.uniquePathsIII(startx, starty, way | (1 << this.index(startx, starty, n)), dp);
	}

	private int uniquePathsIII(int x, int y, int way, Integer[][][] dp) {
		if (x == endx && y == endy) {
			return way == this.limit ? 1 : 0;
		}
		if (dp[x][y][way] != null) {
			return dp[x][y][way];
		}
		int ans = 0;
		for (int i = 0; i < 8; i += 2) {
			int nextx = x + d[i], nexty = y + d[i + 1];
			int nextIndex = this.index(nextx, nexty, n);
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && ((1 << nextIndex) & way) == 0) {
				ans += this.uniquePathsIII(nextx, nexty, way | (1 << nextIndex), dp);
			}
		}
		dp[x][y][way] = ans;
		return ans;
	}

	private int index(int i, int j, int n) {
		return i * n + j;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
